package 力扣.队列;

//import sun.plugin.javascript.navig.Link;

import java.util.*;

// 二叉树结点的定义
class TreeNode {
      TreeNode() {

      }
      TreeNode(int val) {
          this.val = val;
      }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
       }

    // 树结点中的元素值
    int val = 0;

    // 二叉树结点的左子结点
    TreeNode left = null;

    // 二叉树结点的右子结点
    TreeNode right = null;

}
public class 二叉树的层序遍历102 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);

        TreeNode root21 = new TreeNode(9);
        TreeNode root22 = new TreeNode(8);

        TreeNode root31 = new TreeNode(6);
        TreeNode root32 = new TreeNode(7);

        root.left = root21;
        root.right = root22;
        root22.left = root31;
        root22.right = root32;
        List<List<Integer>> lists = levelOrder2(root);
        System.out.println(lists);
    }

    /**
     广度优先搜索：通过队列
       让每一层的‘非空节点‘依次入队，然后’打印结果‘并将节点的’非空子节点‘依次入队
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        Deque<TreeNode> req = new LinkedList<TreeNode>();
        if (root != null){//根节点非空则入队
            req.offer(root);
        }
        while (req.size() > 0){
            final  int size = req.size();
            List<Integer> tes = new LinkedList<>();
            for (int i = 0; i < size; i++) {//遍历当前层
                TreeNode teTree = req.pollFirst();//依次出队
                tes.add(teTree.val);
                if (teTree.left != null){
                    req.offerLast(teTree.left);//入栈，生成下一层
                }
                if (teTree.right != null){
                    req.offerLast(teTree.right);//入栈，生成下一层
                }
            }
            ans.add(tes);
        }
        return ans;
    }

    /**
     广度优先搜索：通过两层List集合
     */
    public static List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();//结果
        List<TreeNode> lts = new ArrayList<>();
        if (root != null){//初始化
            lts.add(root);
        }
        while(!lts.isEmpty()){//lts表示当前层:存放当前层的节点
            List<TreeNode> lts2 = new ArrayList<>();//lts2存放下一层的节点
            List<Integer> tes = new LinkedList<>();//存放当前层的结果
            for (TreeNode teTree : lts) {
                tes.add(teTree.val);
                if (teTree.left != null) {
                    lts2.add(teTree.left);
                }
                if (teTree.right != null) {
                    lts2.add(teTree.right);
                }
            }
            ans.add(tes);
            lts = lts2;//进入到下一层
        }
        return ans;
    }



    public List<List<Integer>> levelOrder3(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        if (root != null){
            deque.add(root);
        }
          while (!deque.isEmpty()){
              int size = deque.size();
              ArrayList<Integer> teList = new ArrayList<>();
              while (size-- > 0){
                  TreeNode treeNode = deque.pollFirst();
                  teList.add(treeNode.val);
                  if (treeNode.left != null){
                      deque.addLast(treeNode.left);
                  }
                  if (treeNode.right != null){
                      deque.addLast(treeNode.right);
                  }
              }
              ans.add(teList);
          }
          return ans;

    }

}
